package hyy_2022;

import commons.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 树的路径总和
 * 使用广度优先搜索(感觉有点像层次遍历，一层一层扫描)
 */
public class _0729_112_TreePathNum {


    /**
     * 给定一个路径和sum,搜索树中根节点到叶子节点是否存在路径和为sum的路径
     * 1、两个队列,一个队列存储将要遍历的节点,一个队列存储根节点到这些节点的路径和
     * @param root
     * @param sum
     * @return boolean
     */
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) {
            return false;
        }
        Queue<TreeNode> queueNode = new LinkedList<>();
        Queue<Integer> queueValue = new LinkedList<>();
        queueNode.offer(root);
        queueValue.offer(root.val);
        while(!queueNode.isEmpty()) {
            TreeNode now = queueNode.poll();
            Integer temp = queueValue.poll();
            if(now.left == null && now.right == null) {
                if(temp == sum) {
                    return true;
                }
                continue;
            }
            queueNode.offer(now.left);
            queueValue.offer(temp + now.left.val);
            queueNode.offer(now.right);
            queueValue.offer(temp + now.right.val);
        }
        return false;
    }
}
